#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <set>
using namespace std;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int> low;
    priority_queue<int,vector<int>,greater<int>> high;
    MedianFinder() {

    }

    void addNum(int num) {
        low.push(num);
        high.push(low.top());
        low.pop();
        if(low.size()<high.size()){
            low.push(high.top());
            high.pop();
        }

    }

    double findMedian() {
        return low.size()>high.size()?(double)low.top():(double)(low.top()+high.top())/2;
    }
};

int main(){
}